﻿/**
 * @file std_queue.c
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 使用 C API 的接口形式实现 FIFO队列 容器。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "std_queue.h"
#include "std_debug.h"
#include "std_queue.inl"

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-function"
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////

//====================================================================

// 
// xstd_queue_t 的内部相关操作接口
// 

/**********************************************************/
/**
 * @brief 计算出适合的 xque_chunk_t 对象缓存大小：2^N 。
 */
static inline xque_size_t queue_chunk_size(xque_this_t xque_this)
{
#if 1
    if (XQUE_ESIZE(xque_this) <= (1 << 4))
    {
        return ((xque_size_t)(1) << 
            ((xque_size_t)(5) - std_ceil2pn(XQUE_ESIZE(xque_this))));
    }
#else
    if (XQUE_ESIZE(xque_this) <= 1)
        return 32;
    else if (XQUE_ESIZE(xque_this) <= 2)
        return 16;
    else if (XQUE_ESIZE(xque_this) <= 4)
        return 8;
    else if (XQUE_ESIZE(xque_this) <= 8)
        return 4;
    else if (XQUE_ESIZE(xque_this) <= 16)
        return 2;
#endif
    return 1;
}

/**********************************************************/
/**
 * @brief 申请分块缓存对象。
 */
static xque_cptr_t queue_chunk_alloc(xque_this_t xque_this)
{
    xque_cptr_t xchk_mptr = xque_this->xchk_rptr;
    if (XQUE_NULL == xchk_mptr)
    {
#if XQUE_CHUNK_SEPARATED

        xchk_mptr = 
            (xque_cptr_t)XQUE_MALLOC(xque_this, XQUE_SIZEOF_CHUNK(xque_this));
        XASSERT(XQUE_NULL != xchk_mptr);

        xchk_mptr->xchk_next = XQUE_NULL;

        xchk_mptr->xchk_dptr = 
            (xstd_bptr_t)XQUE_MALLOC(
                xque_this, xque_this->xchk_size * XQUE_ESIZE(xque_this));
        XASSERT(XQUE_NULL != xchk_mptr->xchk_dptr);

#else // !XQUE_CHUNK_SEPARATED

        xchk_mptr = 
            (xque_cptr_t)XQUE_MALLOC(xque_this, XQUE_SIZEOF_CHUNK(xque_this));
        XASSERT(XQUE_NULL != xchk_mptr);

#endif // XQUE_CHUNK_SEPARATED
    }
    else
    {
        xque_this->xchk_rptr = XQUE_NULL;
    }

    xchk_mptr->xchk_next = XQUE_NULL;
    return xchk_mptr;
}

/**********************************************************/
/**
 * @brief 回收分块缓存对象。
 */
static xque_void_t queue_chunk_recyc(
                        xque_this_t xque_this,
                        xque_cptr_t xchk_mptr)
{
    if (xchk_mptr != xque_this->xchk_rptr)
    {
        if (XQUE_NULL != xque_this->xchk_rptr)
        {
#if XQUE_CHUNK_SEPARATED

            XQUE_DEALLOC(xque_this, xque_this->xchk_rptr->xchk_dptr);
            XQUE_DEALLOC(xque_this, xque_this->xchk_rptr);

#else // !XQUE_CHUNK_SEPARATED

            XQUE_DEALLOC(xque_this, xque_this->xchk_rptr);

#endif // XQUE_CHUNK_SEPARATED
        }
        xque_this->xchk_rptr = xchk_mptr;
    }
}

/**********************************************************/
/**
 * @brief 将前端元素删除后，则将前端位置向前移。
 */
static xque_void_t queue_front_forward(xque_this_t xque_this)
{
    xque_cptr_t xchk_mptr = XQUE_NULL;

    if (++xque_this->xque_front.xchk_npos == xque_this->xchk_size)
    {
        XASSERT(XQUE_NULL != xque_this->xque_front.xchk_mptr);
        XASSERT(XQUE_NULL != xque_this->xque_front.xchk_mptr->xchk_next);

        xchk_mptr = xque_this->xque_front.xchk_mptr;
        xque_this->xque_front.xchk_mptr = xchk_mptr->xchk_next;
        xque_this->xque_front.xchk_npos = 0;

        queue_chunk_recyc(xque_this, xchk_mptr);
    }
}

/**********************************************************/
/**
 * @brief 在后端压入新元素后，将后端位置向前移。
 */
static xque_void_t queue_back_forward(xque_this_t xque_this)
{
    xque_cptr_t xchk_mptr = XQUE_NULL;

    if (++xque_this->xque_back.xchk_npos == xque_this->xchk_size)
    {
        XASSERT(XQUE_NULL != xque_this->xque_back.xchk_mptr);
        XASSERT(XQUE_NULL == xque_this->xque_back.xchk_mptr->xchk_next);

        xchk_mptr = queue_chunk_alloc(xque_this);
        XASSERT(XQUE_NULL != xchk_mptr);
        xque_this->xque_back.xchk_mptr->xchk_next = xchk_mptr;

        xque_this->xque_back.xchk_mptr = xchk_mptr;
        xque_this->xque_back.xchk_npos = 0;
    }
}

//====================================================================

// 
// xstd_queue_t 的外部相关操作接口
// 

/**********************************************************/
/**
 * @brief 返回内部的 sizeof(xstd_queue_t) 值。
 */
xque_size_t std_queue_sizeof(void)
{
    return (xque_size_t)sizeof(xstd_queue_t);
}

/**********************************************************/
/**
 * @brief 创建 xstd_queue_t 对象。
 * @note  应使用 @see std_queue_destroy() 销毁所创建的对象。
 * 
 * @param [in ] xque_ctxt : 队列 所存储的节点元素上下文描述信息。
 * 
 * @return xque_this_t : 返回所创建的 xstd_queue_t 对象指针。
 */
xque_this_t std_queue_create(xque_ctxt_t xque_ctxt)
{
    XASSERT(XQUE_NULL != xque_ctxt);
    XASSERT(0 != xque_ctxt->xstd_etype);
    XASSERT(0 != xque_ctxt->xstd_esize);

    xstd_altor_t xstd_altor = XSTD_ALTOR_NCREF(xque_ctxt->xstd_altor);
    xque_this_t xque_this =
        (xque_this_t)xstd_altor->xfunc_allocate(sizeof(xstd_queue_t));
    XASSERT(XQUE_NULL != xque_this);

    return std_queue_emplace_create(xque_this, xque_ctxt);
}

/**********************************************************/
/**
 * @brief 
 * 销毁 xstd_queue_t 对象，
 * 其由 @see std_queue_create() 接口所创建。
 */
xque_void_t std_queue_destroy(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);

    xstd_altor_t xstd_altor = XQUE_ALTOR(xque_this);

    std_queue_emplace_destroy(xque_this);
    xstd_altor->xfunc_dealloc(xque_this);
}

/**********************************************************/
/**
 * @brief 在指定的缓存上创建 xstd_queue_t 对象。
 * @note
 * 1. 所使用的缓存，其大小应不小于 @see std_queue_sizeof() 的返回值。
 * 2. 销毁对象时，应使用 @see std_queue_emplace_destroy() 接口。
 * 
 * @param [out] xque_this : 创建 xstd_queue_t 对象使用的缓存。
 * @param [in ] xque_ctxt : 队列 所存储的节点元素上下文描述信息。
 * 
 * @return xque_this_t : 返回所创建的 xstd_queue_t 对象指针。
 */
xque_this_t std_queue_emplace_create(
                    xque_this_t xque_this,
                    xque_ctxt_t xque_ctxt)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(XQUE_NULL != xque_ctxt);
    XASSERT(0 != xque_ctxt->xstd_etype);
    XASSERT(0 != xque_ctxt->xstd_esize);

    //======================================

    XQUE_ECTXT_UPDATE(xque_this, xque_ctxt);

    xque_this->xchk_size = queue_chunk_size(xque_this);
    xque_this->xque_size = 0;
    xque_this->xchk_rptr = XQUE_NULL;

    xque_this->xque_front.xchk_mptr = queue_chunk_alloc(xque_this);
    xque_this->xque_front.xchk_npos = 0;
    xque_this->xque_back.xchk_mptr  = xque_this->xque_front.xchk_mptr;
    xque_this->xque_back.xchk_npos  = 0;

    XASSERT(XQUE_NULL != xque_this->xque_front.xchk_mptr);

    //======================================

    return xque_this;
}

/**********************************************************/
/**
 * @brief 
 * 销毁 xstd_queue_t 对象，
 * 其由 @see std_queue_emplace_create() 接口所创建。
 */
xque_void_t std_queue_emplace_destroy(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);

    //======================================

    while (xque_this->xque_size > 0)
    {
        std_queue_pop(xque_this);
    }

    //======================================

    queue_chunk_recyc(xque_this, xque_this->xque_front.xchk_mptr);
    queue_chunk_recyc(xque_this, xque_this->xque_back.xchk_mptr);
    queue_chunk_recyc(xque_this, XQUE_NULL);

    //======================================

    xque_this->xque_front.xchk_mptr = XQUE_NULL;
    xque_this->xque_front.xchk_npos = 0;
    xque_this->xque_back.xchk_mptr  = XQUE_NULL;
    xque_this->xque_back.xchk_npos  = 0;

    //======================================
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象的 上下文信息。
 */
xque_ctxt_t std_queue_ctxt(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    return XQUE_ECTXT(xque_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象的 类型标识。
 */
xque_size_t std_queue_etype(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    return XQUE_ETYPE(xque_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象当前的节点数量。
 */
xque_size_t std_queue_size(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    return xque_this->xque_size;
}

/**********************************************************/
/**
 * @brief 判断 xstd_queue_t 对象是否为空。
 */
xque_bool_t std_queue_empty(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    return (0 == xque_this->xque_size);
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象可容纳最大的节点数量。
 */
xque_size_t std_queue_maxsize(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    return XQUE_MAX_SIZE(xque_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象的前端节点元素。
 */
xque_elem_t std_queue_front(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(xque_this->xque_size > 0);
    return XQUE_FRONT(xque_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_queue_t 对象的后端节点元素。
 */
xque_elem_t std_queue_back(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(xque_this->xque_size > 0);
    return XQUE_BACK(xque_this);
}

/**********************************************************/
/**
 * @brief 向 xstd_queue_t 对象后端压入一个元素。
 * 
 * @param [in,out] xque_this : xstd_queue_t 对象。
 * @param [in    ] xque_elem : 所压入的元素值。
 */
xque_void_t std_queue_push(
                xque_this_t xque_this,
                xque_elem_t xque_elem)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(XQUE_NULL != xque_elem);

    if (xque_this->xque_size > 0)
    {
        queue_back_forward(xque_this);
    }

    XQUE_ALFROM(xque_this, XQUE_BACK(xque_this), xque_elem);
    ++xque_this->xque_size;
}

/**********************************************************/
/**
 * @brief 使用右值 move 方式，向 xstd_queue_t 对象后端压入一个元素。
 * 
 * @param [in,out] xque_this : xstd_queue_t 对象。
 * @param [in    ] xque_elem : 所压入的元素值。
 */
xque_void_t std_queue_mpush(
                xque_this_t xque_this,
                xque_elem_t xque_elem)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(XQUE_NULL != xque_elem);

    if (xque_this->xque_size > 0)
    {
        queue_back_forward(xque_this);
    }

    XQUE_ALMOVE(xque_this, XQUE_BACK(xque_this), xque_elem);
    ++xque_this->xque_size;
}

/**********************************************************/
/**
 * @brief 对  xstd_queue_t 对象的前端元素执行弹出（删除）操作。
 */
xque_void_t std_queue_pop(xque_this_t xque_this)
{
    XASSERT(XQUE_NULL != xque_this);
    XASSERT(0 != xque_this->xque_size);

    XQUE_ALDEST(xque_this, XQUE_FRONT(xque_this));
    if (--xque_this->xque_size > 0)
    {
        queue_front_forward(xque_this);
    }
}

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////
